package com.dy.树与二叉树.二叉树.链式存储;

import jdk.nashorn.internal.ir.BinaryNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BiTree {

    public static void main(String[] args) {
        BiTreeNode d = new BiTreeNode('d');
        BiTreeNode g = new BiTreeNode('g');
        BiTreeNode h = new BiTreeNode('h');
        BiTreeNode e = new BiTreeNode('e',g,null);
        BiTreeNode f = new BiTreeNode('f',null,h);
        BiTreeNode b = new BiTreeNode('b',d,e);
        BiTreeNode c = new BiTreeNode('c',f,null);
        BiTreeNode a = new BiTreeNode('a',b,c);

        System.out.println(衍生算法.searchNode(a,'k').data);

        BiTree t = new BiTree(a);
//        t.preRootTraverse(t.root);
//        System.out.println();
//        t.preRootTraverseNotDigui(t.root);
//        System.out.println();
//        t.inRootTraverse(t.root);
//        System.out.println();
//        t.inRootTraverseNotDigui(t.root);
//
//        System.out.println();
//
//        t.postRootTraverse(t.root);
//        System.out.println();
//        t.levelTraverse(t.root);
    }


    public BiTreeNode root;

    public BiTree() {
    }

    public BiTree(BiTreeNode root) {
        this.root = root;
    }

    //先序遍历,根左右 递归
    public void preRootTraverse(BiTreeNode T) {
        if (T != null) {
            System.out.print(T.data);
            preRootTraverse(T.lchild);
            preRootTraverse(T.rchild);
        }
    }

    //先序遍历 根左右 非递归 栈存右子树
    public void preRootTraverseNotDigui(BiTreeNode r) {
        if (r != null) {
            Stack<BiTreeNode> st = new Stack<>();
            st.push(r);
            while (!st.isEmpty()) {
                BiTreeNode tmp = st.pop();
                System.out.print(tmp.data);

                while (tmp != null) {
                    if (tmp.lchild != null) System.out.print(tmp.lchild.data);
                    if (tmp.rchild != null) st.push(tmp.rchild);
                    tmp = tmp.lchild;
                }

            }
        }
    }
    //

    //中序遍历,左根右 递归
    public void inRootTraverse(BiTreeNode T) {
        if (T != null) {

            inRootTraverse(T.lchild);
            System.out.print(T.data);
            inRootTraverse(T.rchild);
        }
    }

    //中序遍历,左根右 非递归 栈存右子树
    public void inRootTraverseNotDigui(BiTreeNode T) {
        if (T != null) {
            Stack<BiTreeNode> st = new Stack<>();
            st.push(T);
            while (!st.isEmpty()) {
                while (st.peek() != null) {
                    st.push(st.peek().lchild);
                }
                st.pop();//退出空节点
                if (!st.isEmpty()) {
                    T = st.pop();
                    System.out.print(T.data);
                    st.push(T.rchild);
                }
            }

        }
    }

    public void midOrder1(BiTreeNode Node) {
        Stack<BiTreeNode> stack = new Stack<>();
        while (Node != null || !stack.empty()) {
            while (Node != null) {
                stack.push(Node);
                Node = Node.lchild;
            }
            if (!stack.empty()) {
                Node = stack.pop();
                System.out.print(Node.data + "   ");
                Node = Node.rchild;
            }
        }
    }


    //后序遍历,左右跟 递归
    public void postRootTraverse(BiTreeNode T) {
        if (T != null) {

            postRootTraverse(T.lchild);
            postRootTraverse(T.rchild);
            System.out.print(T.data);
        }
    }


    /**
     * 后序遍历
     * 非递归
     */
    public void posOrder1(BiTreeNode Node) {
        Stack<BiTreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int i = 1;
        while (Node != null || !stack1.empty()) {
            while (Node != null) {
                stack1.push(Node);
                stack2.push(0);
                Node = Node.lchild;
            }

            while (!stack1.empty() && stack2.peek() == i) {
                stack2.pop();
                System.out.print(stack1.pop().data + "   ");
            }

            if (!stack1.empty()) {
                stack2.pop();
                stack2.push(1);
                Node = stack1.peek();
                Node = Node.rchild;
            }
        }
    }

    //层序遍历
    public void levelTraverse(BiTreeNode root) {
        if (root != null) {
            Queue<BiTreeNode> queue = new LinkedList<>();
            int current =1;
            int next=0;
            queue.offer(root);
            while (!queue.isEmpty()) {
                root = queue.poll();
                current--;
                System.out.printf("%-4d",root.data);

                if(root.lchild!=null) {
                    queue.offer(root.lchild);
                    next++;
                }
                if(root.rchild!=null) {
                    queue.offer(root.rchild);
                    next++;
                }
                if(current==0){
                    System.out.println();
                    current = next;
                     next = 0;
                }

            }


        }
    }

}
